import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 20:52
 * @description 对于权值存在负数或最短路并不存在的情况，Dijkstra算法将失效，这时候需要采用Bellman-Ford算法
 * 算法核心为松弛操作：对于边 (u,v) 松弛操作为：dis(v) = min(dis(v), dis(u) + w[u][v]))，Dijkstra中同样采用
 * Bellman-Ford算法不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。
 * 在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 + 1，而最短路的边数最多为 n - 1 ，因此整个算法最多执行 n - 1 轮松弛操作。
 * 如果第 n 轮循环时仍然存在能松弛的边，说明从 S 点出发，能够抵达一个负环。
 */
public class BellmanFord {
    /**
     * 存储图
     */
    List<int[]>[] graph;
    /**
     * 存储源点到其他点的最短路
     */
    int[] dis;
    /**
     * 正无穷
     */
    int INF = Integer.MAX_VALUE / 2;

    /**
     * 求最短路并判断通过s能够到达一个负环
     * @param n n个结点，编号 0..n-1
     * @param s 源点s
     * @param edges u e[0] v e[1] w(u,v) = e[2]
     * @return 是否存在负环
     */
    public boolean bellmanFord(int n, int s, int[][] edges ) {
        // 1. 初始化邻接表
        graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e: edges) {
            graph[e[0]].add(new int[]{e[1], e[2]});
        }
        // 2. 初始化源点s 到 其他点的最短路
        dis = new int[n];
        Arrays.fill(dis, INF);
        dis[s] = 0;

        // 3. flag标志，判断一轮循环过程中是否发生松弛操作
        boolean flag = false;

        // 4. bellman-Ford
        for (int i = 0; i < n; i++) {
            flag = false;
            for (int u = 0; u < n; u++) {
                // 无穷大与常数加减仍然为无穷大
                // 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
                if (dis[u] == INF) {
                    continue;
                }
                for (int[] e: graph[u]) {
                    int v = e[0], w = e[1];
                    if (dis[u] + w < dis[v]) {
                        dis[v] = dis[u] + w;
                        flag = true;
                    }
                }
            }
            // 没有可以松弛的边就停止算法
            if (!flag) {
                break;
            }
        }
        // 第 n 轮循环仍然可以松弛说明s点可以抵达一个负环
        return flag;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1, 1}, {0, 2, 2},  {0, 3, 3}, {0, 4,4}};
        BellmanFord solution = new BellmanFord();
        solution.bellmanFord(5, 0, edges);
        System.out.println(Arrays.toString(solution.dis));

        int[][] ed = {{0, 1, 5}, {1, 2, -3}, {2, 3, 1}, {3, 1, 1}, {1, 4, 6}};
        BellmanFord solution2 = new BellmanFord();
        solution2.bellmanFord(5, 0, ed);
        System.out.println(Arrays.toString(solution2.dis));
    }
}
